/*
 * @lc app=leetcode.cn id=662 lang=javascript
 *
 * [662] 二叉树最大宽度
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
* @param {TreeNode} root
* @return {number}
*/
var widthOfBinaryTree = function (root) {
  if (!root) return 0;

  let stack = [[0n, root]];
  let max = 1n;

  while (stack.length) {
    let width = stack[stack.length - 1][0] - stack[0][0] + 1n;
    if (width > max) max = width;

    let temp = [];
    for (const [i, q] of stack) {
      q.left && temp.push([i * 2n, q.left]);
      q.right && temp.push([i * 2n + 1n, q.right]);
    }
    stack = temp;
  }
  return Number(max);
};


var widthOfBinaryTree = function (root) {
  if (!root) return 0;
  let arr = [[0, 0]];
  let max = 0;

  function getNode(root, arr, k) {
    if (!root) return;

    if (!arr[k]) arr[k] = [];

    arr[k][0] = arr[k - 1][0] * 2 + 1;
    arr[k][1] = root.right ? arr[k - 1][1] * 2 + 2 : arr[k][0];

    getNode(root.left, arr, k + 1);
    getNode(root.right, arr, k + 1);
    if (arr[k][1] - arr[k][0] + 1 > max) max = arr[k][1] - arr[k][0] + 1;
    console.log(arr[k]);
  }

  getNode(root, arr, 1);
  console.log(arr);
  return max;
};
// @lc code=end

